package com.sicheng.lc.周赛.分类.哈西表or计数or滑动窗口or双指针.双指针;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/9 21:39
 */
public class 最短无序连续子数组 {
    //https://leetcode.cn/problems/shortest-unsorted-continuous-subarray/
    public int findUnsortedSubarray(int[] nums) {

        int l = 0, r = nums.length - 1;
        while (r > 0 && nums[r - 1] <= nums[r]) r--;
        if (r == 0)
            return 0;

        while (l + 1 < nums.length && nums[l] <= nums[l + 1]) l++;
        int min = Integer.MAX_VALUE;
        int max = -min;
        for (int i = l ; i <= r; i++) {
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]);
        }
        int x = rightSearch(nums, min, l);
        int y = leftSearch(nums, max, r, nums.length - 1);
        return y - x + 1;
    }

    int leftSearch(int[] nums, int x, int L, int R) {
        int l = L, r = R;
        while (l <= r) {
            int mid = l + r >> 1;
            if (nums[mid] >= x) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return l - 1;
    }

    int rightSearch(int[] nums, int x, int R) {
        int l = 0, r = R;
        while (l <= r) {
            int mid = l + r >> 1;
            if (nums[mid] <= x) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }

    public static void main(String[] args) {
        最短无序连续子数组 s = new 最短无序连续子数组();
        int[] nums = {2, 6, 4, 8, 10, 9, 15};
        System.out.println(s.findUnsortedSubarray(nums));
    }
}
